Crate iset

source ·
Expand description

This crates implements map and set with interval keys (ranges x..y).

IntervalMap is implemented using red-black binary tree, where each node contains information about the smallest start and largest end in its subtree. The tree takes O(N) space and allows insertion, removal and search in O(log N). IntervalMap allows to search for all entries overlapping a query (interval or a point, output would be sorted by keys) in O(log N + K) where K is the size of the output.

IntervalSet is a newtype over IntervalMap with empty values.

Features

By default, iset is no_std. Three optional features are:

  • std: no additional effects,
  • serde: Serialization/Deserialization (requires std environment),
  • dot: allows to write interval maps and sets to .dot files (requires std).

Re-exports

Modules

  • Module with various iterators over IntervalMap and IntervalSet.
  • Wrapper around integer types, used as indices within IntervalMap and IntervalSet.
  • IntervalSet implementation.

Macros

Structs